% Figure 12.3  A best-first search program.


% bestfirst( Start, Solution): Solution is a path from Start to a goal

bestfirst(Start, Solution) :-
	expand([], l(Start, 0/0), 9999, _, yes, Solution).
	%  Assume 9999 is greater than any f-value

% expand( Path, Tree, Bound, Tree1, Solved, Solution):
%   Path is path between start node of search and subtree Tree,
%   Tree1 is Tree expanded within Bound,
%   if goal found then Solution is solution path and Solved = yes

%  Case 1: goal leaf-node, construct a solution path

expand(P, l(N, _), _, _, yes, [N|P])  :-
	goal(N).

%  Case 2: leaf-node, f-value less than Bound
%  Generate successors and expand them within Bound.

expand(P, l(N,F/G), Bound, Tree1, Solved, Sol)  :-
	F  =<  Bound,
	(bagof(M/C, (s(N,M,C), not(member(M,P)) ), Succ), 
     !,                                   % Node N has successors
     succlist(G, Succ, Ts),               % Make subtrees Ts
     bestf(Ts, F1),                       % f-value of best successor
     expand(P, t(N,F1/G,Ts), Bound, Tree1, Solved, Sol)
     ;
     Solved = never                       % N has no successors - dead end
	) .

%  Case 3: non-leaf, f-value less than Bound
%  Expand the most promising subtree; depending on 
%  results, procedure continue will decide how to proceed

expand(P, t(N,F/G,[T|Ts]), Bound, Tree1, Solved, Sol)  :-
  F  =<  Bound,
  bestf(Ts, BF), min(Bound, BF, Bound1),          % Bound1 = min(Bound,BF)
  expand([N|P], T, Bound1, T1, Solved1, Sol),
  continue(P, t(N,F/G,[T1|Ts]), Bound, Tree1, Solved1, Solved, Sol).

%  Case 4: non-leaf with empty subtrees
%  This is a dead end which will never be solved

expand(_, t(_,_,[]), _, _, never, _) :- !.

%  Case 5:  f-value greater than Bound
%  Tree may not grow.

expand(_, Tree, Bound, Tree, no, _)  :-
  f(Tree, F), F > Bound.

% continue( Path, Tree, Bound, NewTree, SubtreeSolved, TreeSolved, Solution)

continue(_, _, _, _, yes, yes, Sol).

continue(P, t(N,F/G,[T1|Ts]), Bound, Tree1, no, Solved, Sol)  :-
	insert(T1, Ts, NTs),
	bestf(NTs, F1),
	expand(P, t(N,F1/G,NTs), Bound, Tree1, Solved, Sol).

continue(P, t(N,F/G,[_|Ts]), Bound, Tree1, never, Solved, Sol)  :-
	bestf(Ts, F1),
	expand(P, t(N,F1/G,Ts), Bound, Tree1, Solved, Sol).

% succlist( G0, [ Node1/Cost1, ...], [ l(BestNode,BestF/G), ...]):
%   make list of search leaves ordered by their F-values

succlist(_, [], []).

succlist(G0, [N/C | NCs], Ts)  :-
	G is G0 + C,
	h(N, H),                             % Heuristic term h(N)
	F is G + H,
	succlist(G0, NCs, Ts1),
	insert(l(N,F/G), Ts1, Ts).

% Insert T into list of trees Ts preserving order w.r.t. f-values

insert(T, Ts, [T | Ts])  :-
	f(T, F), bestf(Ts, F1),
	F  =<  F1, !.

insert(T, [T1 | Ts], [T1 | Ts1])  :-
	insert(T, Ts, Ts1).


% Extract f-value

f(l(_,F/_), F).        % f-value of a leaf

f(t(_,F/_,_), F).      % f-value of a tree

bestf([T|_], F)  :-    % Best f-value of a list of trees
	f(T, F).

bestf([], 9999).       % No trees: bad f-value
  
min(X, Y, X)  :-
	X  =<  Y, !.

min(X, Y, Y).

% My example model of the graphs from the first part of the course
s(a,b,1).
s(a,f,2).
s(a,e,3).

s(b,a,1).
s(b,g,4).
s(b,c,5).

s(c,b,5).
s(c,h,6).
s(c,d,7).

s(d,c,7).
s(d,i,8).
s(d,e,9).

s(e,d,9).
s(e,j,1).
s(e,a,3).

s(f,g,2).
s(f,a,2).
s(f,j,3).

s(g,f,2).
s(g,b,4).
s(g,h,4).

s(h,g,4).
s(h,c,6).
s(h,i,5).

s(i,h,5).
s(i,d,8).
s(i,j,6).

s(j,i,6).
s(j,e,1).
s(j,f,3).

goal(j).

% Heuristic estimates
h(a,8).
h(b,7).
h(c,9).
h(d,5).
h(e,1).
h(f,3).
h(g,2).
h(h,4).
h(i,6).
h(j,0).